package 背包问题;

public class 递归方式的01背包问题解法 {

    // 记忆化搜索的数组是二维的
    // 因为背包问题被 w 和 v 两个变量控制着
    // 要记忆
    int[][] dp;

    /**
     * 首先该算法的重点是：
     * 【从前往后选择物品加入背包，和从后往前加入物品到背包，以及打乱顺序从任意位置选择物品加入背包的最终结果都是一样的】
     * 并且在递归的过程中存在重叠子问题，所以应该自下而上求解
     * 那么对应到这里就是【从后往前】选择物品放入背包，同时用【辅助数组存储已经计算出来的解】
     * <p>
     * 状态转移方程：
     * f(i, c) = Max(f(i-1, c), f(i-1, c-w[i])+v[i])
     * <p>
     * 方程含义的解释：
     * f(i, c) 表示把 i 个物品放入容量为 c 的背包里面的价值最大
     * 那么要获取 f(i) 的最大值，前提是先获取到 f(i-1) 的最大价值
     * 而这个 f(i-1) 的最大价值又是通过前一个得到的
     * 并且这个 f(i-1) 的最大价值可能是因为前一个物品放入背包了得到的，也可能是前一个物品没有放入背包
     * 所以背包问题的状态转移方程要这么写
     *
     * @param w 物品的重量
     * @param v 物品的价值
     * @param c 背包的容量，例如容量是对重量的限制
     * @return 最大价值
     */
    public int knapsack01(int[] w, int[] v, int c) {
        int n = w.length;
        dp = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                dp[i][j] = -1;
            }
        }

        // 既然是递归处理，所以先创建一个递归函数
        // 该函数从最后一个背包开始
        return bestValue(w, v, n - 1, c);
    }

    // 用 [0...index] 的物品，填充容积为 c 的背包的最大价值
    public int bestValue(int[] w, int[] v, int index, int c) {
        // 若待寻找的背包越界，或者背包满了
        if (index < 0 || c <= 0)
            return 0; // 装不下任何东西，也就是价值为0
        /*
        index 和 c 构成的数据对会在递归的过程中产生重叠子问题
        所以可以存储 index 和 c 构成的数据对的计算结果
         */
        if (dp[index][c] != -1)
            return dp[index][c];

        /*
        下一个选择的物品可能要，也可能不要，所以要求价值的 max
         */

        // 这是不要的情况
        int res = bestValue(w, v, index - 1, c);
        // 这是要的情况，要的话得先判断剩余的背包空间还能装下该物品
        if (c >= w[index]) {
            res = Math.max(res, bestValue(w, v, index - 1, c - w[index]) + v[index]);
        }
        // 写入缓存
        dp[index][c] = res;
        return res;
    }


    public static void main(String[] args) {

        int[] weight = {2, 2, 6, 5, 4};
        int[] value = {6, 3, 5, 4, 6};
        int c = 10;
        递归方式的01背包问题解法 instance = new 递归方式的01背包问题解法();
        System.out.println(instance.knapsack01(weight, value, c)); // 15

    }
}
